1. Field of the Invention
In general, this invention relates to a disk-based storage system; more particularly, it relates to such a system that receives a direction-selection signal and autonomously controls seeks in a sequence determined by the direction-selection signal and a locally-stored doubly linked list.
2. Description of the Related Art
A number of related markets exist for disk-based storage systems for supporting the playback of data streams such as audio/visual (xe2x80x9cA/Vxe2x80x9d) streams. Among these are markets for image repositories, video on demand, networked video, and consumer TV time shifting.
Disk-based storage systems designed for these markets are described in various patents. Among these are: U.S. Pat. No. 5,701,383, titled xe2x80x9cVIDEO TIME-SHIFTING APPARATUSxe2x80x9d; U.S. Pat. No. 5,519,435, titled xe2x80x9cMULTI-USER, ON-DEMAND VIDEO STORAGE AND RETRIEVAL SYSTEM INCLUDING VIDEO SIGNATURE COMPUTATION FOR PREVENTING EXCESSIVE INSTANTANEOUS SERVER DATA RATExe2x80x9d; U.S. Pat. No. 5,737,747, titled xe2x80x9cPREFETCHING TO SERVICE MULTIPLE VIDEO STREAMS FROM AN INTEGRATED CACHED DISK ARRAYxe2x80x9d; and U.S. Pat. No. 5,892,915, titled xe2x80x9cSYSTEM HAVING CLIENT SENDING EDIT COMMANDS TO SERVER DURING TRANSMISSION OF CONTINUOUS MEDIA FROM ONE CLIP IN PLAY LIST FOR EDITING THE PLAY LIST.xe2x80x9d
A performance requirement for substantially all such disk-based storage systems is to respond to user control. As used herein, the term xe2x80x9cuser controlxe2x80x9d refers to inputs provided by the user or operator (such as xe2x80x9cplay,xe2x80x9d xe2x80x9cfast forward,xe2x80x9d xe2x80x9cpause,xe2x80x9d xe2x80x9crewind,xe2x80x9d etc.). The xe2x80x9cplayxe2x80x9d item indicates a forward direction and the xe2x80x9crewindxe2x80x9d item indicates a reverse direction. A market requirement for substantially all such disk-based storage systems is to be cost effective, whereby a mass market consumer system needs to be extremely low in cost, but even a high-performance broadcast-market system needs to be cost competitive.
A problem commonly arising in the disk-based systems designed for these markets relates to reducing command-protocol latency and doing so in a cost-effective way.
With respect to cost effectiveness, a system design benefits from incorporating component subsystems that are, or are easily-modified versions of, mass-produced products. This is the case even in high-performance broadcast-market systems, as indicated in some of the above-identified patents that emphasize the advantage of building the system with component subsystems that constitute or are derived from commodity products such as commodity personal computers and commodity disk drives.
With respect to command-protocol latency, a system design benefits from reducing such latency, thereby to provide more bandwidth for handling the core functions needed for streaming. Command-protocol latency generally includes a number of elements that can be described with reference to communication between disk-drive structure and host structure. The term host structure is used in a very broad sense and includes without limitation standalone structure such as the commodity computers described as stream servers in some of the above-identified patents, and other structure such as programmable microprocessor-based circuitry integrated into the front end of a disk-based storage system such as that disclosed in U.S. Pat. No. 5,802,069, titled xe2x80x9cIMPLEMENTING MASS STORAGE DEVICE FUNCTIONS USING HOST PROCESSOR MEMORY,xe2x80x9d or in U.S. Pat. No. 5,809,337, titled xe2x80x9cMASS STORAGE DEVICES UTILIZING HIGH SPEED SERIAL COMMUNICATIONS,xe2x80x9d or in published European Patent Application No. EP 0 757 310 A2, titled xe2x80x9cCONTROLLING DISK DRIVES,xe2x80x9d (this published application describing a disk drive in column 11, lines 22 et seq., which includes a disk scheduler as part of an integrated disk drive. For brevity hereinafter, such host structure is referred to as a xe2x80x9chost.xe2x80x9d Similarly, the term xe2x80x9cdisk-drive structurexe2x80x9d is used in a very broad sense to encompass hard disk drives having industry-standard interfaces such as IDE, SCSI, 1394, etc., and also to encompass head disk assemblies (xe2x80x9cHDA""sxe2x80x9d) and associated electronics such portions of integrated drive/host systems; such disk-drive structure is hereinafter sometimes briefly referred to as a xe2x80x9cdrive.xe2x80x9d
Command-protocol latency includes a number of elements. One of these elements is a software-associated latency relating to execution of instructions to organize and issue a host command. Two other elements are latencies that relate to the transmission and reception of the command while it propagates from the host and while it is received by the drive. An additional element relates to the latency involved in parsing of the command by the drive. For additional background regarding command-protocol latency, see U.S. Pat. No. 4,851,998, titled xe2x80x9cMETHOD FOR ANALYZING PERFORMANCE OF COMPUTER PERIPHERALSxe2x80x9d; note particularly FIG. 2 and column 4, lines 22-54.
As for certain high-performance broadcast-market systems, the prior art (such as U.S. Pat. No. 5,892,915 cited above and hereinafter referred to as the ""915 patent) teaches a hierarchical arrangement involving multiple levels of command-protocol latency. As shown in FIG. 28 of the ""915 patent, the described system includes, at a first level of the hierarchy, a controller server; at a second level of the hierarchy, a stream server; and at a third level of the hierarchy, a cached disk array. Each of the controller servers and each of the stream servers is described as being a high-end commodity computer including an Intel processor such as a Pentium and including substantial amount of random access memory (RAM) such as 64 megabytes.
The hierarchical arrangement of the ""915 patent involves a distribution among the levels of certain important control functions associated with storing control data, and involves communications between the various levels in which communications there are numerous dialogs and control-data transfers. In accord with this distribution important lists of control data are stored remotely from the drives in the cached disk array. These remotely stored lists are the subject of the following dialogs and control-data transfers between the various levels: One such dialog and transfer is the sending and delivery of a remotely-stored stripe set list from the controller server to a selected one of the steam servers. The controller server maintains a clip directory and numerous such remotely-stored stripe set lists. Each remotely-stored stripe set list is associated with a respective clip identified in the clip directory. Each remotely-stored stripe set list includes a doubly-linked list of entries, and each entry includes a starting stripe set number, an ending stripe set number, and a value indicating the number of data segments included in the terminal stripe set. Therefore, each entry in the list represents in sequence data segments beginning in the initial stripe set, continuing in any intermediate stripe set, and ending in the terminal stripe set. Multiple other such dialogs and transfers occur as the stream server controls the cached disk array. Each stream server remotely maintains a pointer to the current play position in the clip it is currently controlling for a client. The stream server repeatedly issues prefetch commands to the cached disk array so that the succession of stripe sets 325 are prefetched one by one from the drives in the cached disk array. The command-protocol latencies involved are significant factors adversely affecting the overall performance of the system.
This invention can be regarded as a disk-based storage system for storing a plurality of data segments and for responding to a direction-selection signal by autonomously providing the data segments in a selected sequence so as to be concatenated together to define a continuous data stream. The direction-selection signal is preferably defined in response to user control for selecting direction including xe2x80x9cforwardxe2x80x9d corresponding to xe2x80x9cplayxe2x80x9d for an A/V stream; the form of the direction-control signal is subject to a broad range including but not limited to multi-bit commands (whether serial or parallel), or a binary-valued logic signal, or other form of signal. The disk-based storage system comprises nonvolatile storage means including rotating disk media having a plurality of addressable locations. Each of the data segments is stored in a respective one of the addressable locations. Each of the addressable locations has a leading end and a trailing end. As used herein, the terms xe2x80x9cleadingxe2x80x9d and xe2x80x9ctrailingxe2x80x9d refer to those portions of an addressable location or of a data structure or field which are first and last to encounter a given read/write head, respectively, based on a given rotation of rotating media.
A first one of the addressable locations has a trailing end on a first track, and a second one of the addressable locations has a leading end on a second track, the second track being spaced from the first track.
Significantly, the non-volatile storage means includes means locally storing a doubly-linked list of pointers. Preferably, the doubly-linked list of pointers is stored in the disk media.
The disk-based storage system also comprises accessing means controllable to seek to, and access, any of the addressable locations starting at the leading end and continuing through the trailing end.
Significantly, the disk-based storage system also comprises controller means for causing the accessing means to read the data segments in accordance with a sequence determined by the doubly-linked list of pointers and the direction-selection signal. The controller means includes autonomously-operating control means responsive to the trailing end of the first one of the locations having been read for causing the accessing means to seek to the second track.
Embodiments of the invention have significant advantages including an advantage with respect to providing enabling technology for reducing command-protocol latency and doing so in a cost-effective way.
In one embodiment, a disk-based storage system according to the invention receives an record control signal, and thereafter receives a continuous stream of digital data. The disk-based storage system autonomously divides the continuous stream into segments. Significantly, the disk-based storage system autonomously generates the doubly-linked list of pointers for subsequent use in reproducing the continuous stream.
The pointers have address fields and optionally other useful information (such as status flags) which allow the disk-based storage system to operate autonomously using locally stored information to reconstruct a desired sequence of segments without adverse overhead occasioned by command-protocol latency.
Preferably, the pointers are generated based on a deterministic algorithm which accounts for the seek, rotational, and head switching latencies associated with the disk drive, and maintains such latencies within predefined limits.
In an alternative embodiment of the invention, the nonvolatile storage means includes random access memory such as flash memory, and the pointers are stored within the random access memory.
Suitably, the rotating disk media comprises a plurality of magnetic hard disks included in a hard disk drive which also includes a microcontroller, a disk controller, a buffer memory, an I/O processor and an I/O interface. When receiving data via the I/O interface, the disk controller and microcontroller cooperate to dynamically generate the pointers for each incoming data segment and write them to the media with associated data segments. Address locations for the data segments in each data stream is chosen so as to maintain the latency associated with the storage and retrieval of the streaming data within predefined limits. When reading data from the disk media, the disk controller and microcontroller read the pointers associated with each data segment, and in response read the outgoing data stream in sequence.
Another preferred feature involves an improved digital data structure useful in streaming operations. In one embodiment, the data structure involves an identification (ID) field, a data segment, and one or more head-directed and/or tail-directed pointers associated or appended to the data segment. Preferably, each of the pointers has a physical address (head, sector, cylinder or logical block address (LBA) and one or more xe2x80x9ctagxe2x80x9d bits. The tag bits convey information about the associated individual data segment or digital data stream. In this manner, the data structure is self-defining. In one embodiment of the data structure, the pointers are embedded within the data segment. In another embodiment, the pointers are appended to or within the servo wedge.
Another preferred feature involves a method of storing and/or retrieving multiple digital data streams. According to this feature, the disk media are pre-formatted for a pre-selected number of different data streams, such that the latency between streams is kept below a desired value.
Another preferred feature involves an improved method of editing. According to this feature, the method comprises identifying the address of predecessor and successor blocks to the data segment being edited, and modifying the pointers associated with the predecessor and successor blocks so as to reflect the addition or deletion of the edited data segments. The method comprises identifying the predecessor and successor data segments for the first and last data segments in the data stream being edited, and modifying the pointers associated with those blocks to reflect the addresses of the first and last data segments in the data stream.
Another preferred feature involves a pointer error correction method. According to this feature, the error correction method comprises signaling the buffer manager when an uncorrectable pointer error occurs; retrying to correct the error; applying the pointer generation algorithm to generate the next logical seek address and an associated head-directed pointer for that address; and testing the head-directed pointer in the generated data segment.